package ahu.zdw.com;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/3/22 21:10
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 */
public class _53_maxSubArray {
    public static void main(String[] args) {
        Solution solution = new _53_maxSubArray().new Solution();
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        for(int x : nums){
            System.out.println(x);
        }
//        int res = solution.maxSubArray(nums);
//        System.out.println(res);
    }

    // 自己不会做
    class Solution1 {
        public int maxSubArray(int[] nums) {
            if(nums.length==1) return nums[0];
            int[] subSum = new int [nums.length];
            for(int i=1; i<=nums.length; i++){ // 子数组的长度 1~nums.length
                int sum = 0;
                for(int j=0; j<i; j++){
                    sum += nums[j];
                }
                subSum[i-1] = sum;
            }
            int max = nums[0];
            int min = nums[0];
            for(int i=0; i<nums.length; i++){
                if(subSum[i]>max){
                    max = subSum[i];
                }
                if(subSum[i]<min){
                    min = subSum[i];
                }
            }
            if(min<0){
                return max - min;
            }else{
                return max;
            }
        }
    }

    // 官方答案
    class Solution {
        public int maxSubArray(int[] nums) {
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
    }

}
